3SAT problem

Definition

Denote by $\mathtt{3SAT}$ the language of all satisfiable 3CNF formulae.

(see SAT problem)

Notes

• $\mathtt{3SAT} \in$ NP
• $\mathtt{3SAT} \in$ PSPACE
• $\mathtt{3SAT}$ is NP-complete
• SAT reduces to $\mathtt{3SAT}$ in polynomial time, i.e. $\mathtt{SAT} \leq_p \mathtt{3SAT}$
• it is a simple example of a constraint satisfaction problem

References

1. S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, pp. 45, 81-82.
2. https://cstheory.stackexchange.com/questions/7213/direct-sat-to-3-sat-reduction
3. https://ocw.mit.edu/courses/6-045j-automata-computability-and-complexity-spring-2011/567d75f927ca3c11a819baee9ab260ac_MIT6_045JS11_lec16.pdf
4. https://cse.iitkgp.ac.in/~palash/2018AlgoDesignAnalysis/SAT-3SAT.pdf